// 给定一个数组，请你编写一个函数，返回该数组排序后的形式。


// 手撕快排

#include<bits/stdc++.h>
using namespace std;

class Solution
{
private:
    /* data */
public:
    vector<int> MySort(vector<int>& arr) {
        // write code here
        int l=0;
        int r=arr.size()-1;
        quickSort(arr,l,r);
        return arr;
    }

    void quickSort(vector<int>& arr,int l,int r){
        if(l>=r){
            return;
        }
        int first=l;
        int end=r;
        int key=arr[first];
        while(first<end){
            while(first<end && arr[end]>key){
                --end;
            }
            arr[first] = arr[end];
            while (first<end && arr[first]<=key){
                ++first;
            }
            arr[end]=arr[first];
        }
        arr[first]=key;
        quickSort(arr,l,first-1);
        quickSort(arr,first+1,r);
    }
};



int main(int argc, char const *argv[])
{
    vector<int> arr={5,2,3,1,4,8};
    Solution s;
    s.MySort(arr);
    for(auto x:arr){
        cout<<x<<" ";
    }
    cout<<endl;
    return 0;
}
